home *** CD-ROM | disk | FTP | other *** search
/ Super PC 31 / Super PC 31 (Shareware).iso / spc / inter / speakf / fuente / idea / idea.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-08-24  |  24.4 KB  |  815 lines
  1. /* idea.c - C source code for IDEA block cipher. IDEA (International Data 
  2.  * Encryption Algorithm), formerly known as IPES (Improved Proposed Encryption
  3.  * Standard). Algorithm developed by Xuejia Lai and James L. Massey, of ETH 
  4.  * Zurich. This implementation modified and derived from original C code 
  5.  * developed by Xuejia Lai. Zero-based indexing added, names changed from IPES
  6.  * to IDEA. CFB functions added. Random number routines added. Optimized for 
  7.  * speed 21 Oct 92 by Colin Plumb <colin@nsq.gts.org>. This code assumes that 
  8.  * each pair of 8-bit bytes comprising a 16-bit word in the key and in the 
  9.  * cipher block are externally represented with the Most Significant Byte 
  10.  * (MSB) first, regardless of internal native byte order of the target CPU.  */
  11.  
  12. #ifdef TEST
  13. #include <stdio.h>
  14. #include <time.h>
  15. #endif
  16.  
  17. #ifdef sgi
  18. #define HIGHFIRST
  19. #endif
  20.  
  21. #ifdef sun
  22. #define HIGHFIRST
  23. #define const
  24. #endif
  25.  
  26. #include "idea.h"
  27.  
  28. #define FAR    IFAR
  29.  
  30. #ifdef _M_I86
  31. #define USE_ASM
  32. #endif
  33.  
  34. #define min(x, y) (((x) < (y)) ? (x) : (y))
  35.  
  36. #define TRUE    1
  37. #define FALSE    0
  38.  
  39. #define IDEABLOCKSIZE 8
  40. #define ROUNDS      8               /* Don't change this value, should be 8 */
  41. #define KEYLEN        (6*ROUNDS+4)    /* length of key schedule */
  42.  
  43. #define byte    unsigned char
  44. #define word16    unsigned short
  45. #define boolean int
  46. #define word32    unsigned long
  47. #define byteptr unsigned char FAR *
  48.  
  49. typedef word16 IDEAkey[KEYLEN];
  50.  
  51. #ifdef IDEA32 /* Use >16-bit temporaries */
  52. #define low16(x) ((x) & 0xFFFF)
  53. typedef unsigned int uint16;        /* at LEAST 16 bits, maybe more */
  54. #else
  55. #define low16(x) (x)                /* this is only ever applied to uint16's */
  56. typedef word16 uint16;
  57. #endif
  58.  
  59. #ifdef _GNUC_
  60. /* __const__ simply means there are no side effects for this function,
  61.  * which is useful info for the gcc optimizer */
  62. #define CONST __const__
  63. #else
  64. #define CONST
  65. #endif
  66.  
  67. static void en_key_idea(word16 *userkey, word16 *Z);
  68. static void de_key_idea(IDEAkey Z, IDEAkey DK);
  69.  
  70. /* Multiplication, modulo (2**16)+1. Note that this code is structured like 
  71.  * this on the assumption that untaken branches are cheaper than taken 
  72.  * branches, and the compiler doesn't schedule branches. */
  73.  
  74. #ifdef SMALL_CACHE
  75. CONST static uint16 mul(register uint16 a, register uint16 b)
  76. {
  77.        register word32 p;
  78.        if (a)
  79.        {     if (b)
  80.              {        p = (word32)a * b;
  81.                     b = low16(p);
  82.                     a = p>>16;
  83.                     return b - a + (b < a);
  84.              }
  85.              else
  86.              {        return 1-a;
  87.              }
  88.        }
  89.        else
  90.        {     return 1-b;
  91.        }
  92. }
  93. #endif /* SMALL_CACHE */
  94.  
  95. /* Compute multiplicative inverse of x, modulo (2**16)+1, using Euclid's GCD 
  96.  * algorithm. It is unrolled twice to avoid swapping the meaning of the 
  97.  * registers each iteration; some subtracts of t have been changed to adds.  */
  98.  
  99. CONST static uint16 inv(uint16 x)       
  100. {
  101.        uint16 t0, t1;
  102.        uint16 q, y;
  103.        if (x <= 1)
  104.              return x;      /* 0 and 1 are self-inverse */
  105.        t1 = 0x10001 / x;  /* Since x >= 2, this fits into 16 bits */
  106.        y = 0x10001 % x;
  107.        if (y == 1)
  108.              return low16(1-t1);
  109.        t0 = 1;
  110.        do
  111.        {     q = x / y;
  112.              x = x % y;
  113.              t0 += q * t1;
  114.              if (x == 1)
  115.                     return t0;
  116.              q = y / x;
  117.              y = y % x;
  118.              t1 += q * t0;
  119.        } while (y != 1);
  120.        return low16(1-t1);
  121. }
  122.  
  123. /*       Compute IDEA encryption subkeys Z */
  124.  
  125. static void en_key_idea(word16 *userkey, word16 *Z)
  126. {
  127.        int i,j;
  128.        /* shifts */
  129.        for (j=0; j<8; j++)
  130.              Z[j] = *userkey++;
  131.        for (i=0; j<KEYLEN; j++)
  132.        {     i++;
  133.              Z[i+7] = Z[i & 7] << 9 | Z[i+1 & 7] >> 7;
  134.              Z += i & 8;
  135.              i &= 7;
  136.        }
  137. }
  138.  
  139. /*       Compute IDEA decryption subkeys DK from encryption subkeys Z */
  140. /* Note: these buffers *may* overlap! */
  141.  
  142. static void de_key_idea(IDEAkey Z, IDEAkey DK)
  143. {
  144.        int j;
  145.        uint16 t1, t2, t3;
  146.        IDEAkey T;
  147.        word16 *p = T + KEYLEN;
  148.        t1 = inv(*Z++);
  149.        t2 = -*Z++;
  150.        t3 = -*Z++;
  151.        *--p = inv(*Z++);
  152.        *--p = t3;
  153.        *--p = t2;
  154.        *--p = t1;
  155.        for (j = 1; j < ROUNDS; j++)
  156.        {
  157.              t1 = *Z++;
  158.              *--p = *Z++;
  159.              *--p = t1;
  160.              t1 = inv(*Z++);
  161.              t2 = -*Z++;
  162.              t3 = -*Z++;
  163.              *--p = inv(*Z++);
  164.              *--p = t2;
  165.              *--p = t3;
  166.              *--p = t1;
  167.        }
  168.        t1 = *Z++;
  169.        *--p = *Z++;
  170.        *--p = t1;
  171.        t1 = inv(*Z++);
  172.        t2 = -*Z++;
  173.        t3 = -*Z++;
  174.        *--p = inv(*Z++);
  175.        *--p = t3;
  176.        *--p = t2;
  177.        *--p = t1;
  178. /* Copy and destroy temp copy */
  179.        for (j = 0, p = T; j < KEYLEN; j++)
  180.        {
  181.              *DK++ = *p;
  182.              *p++ = 0;
  183.        }
  184. }
  185.  
  186. /* MUL(x,y) computes x = x*y, modulo 0x10001. Requires two temps, t16 and t32.
  187.  * x must me a side-effect-free lvalue. y may be anything, but unlike x, must 
  188.  * be strictly 16 bits even if low16() is #defined. All of these are 
  189.  * equivalent; see which is faster on your machine.  */
  190.  
  191. #ifdef SMALL_CACHE
  192. #define MUL(x,y) (x = mul(low16(x),y))
  193. #else
  194. #ifdef AVOID_JUMPS
  195. #define MUL(x,y) (x = low16(x-1), t16 = low16((y)-1), \
  196.              t32 = (word32)x*t16+x+t16+1, x = low16(t32), \
  197.              t16 = t32>>16, x = x-t16+(x<t16) )
  198. #else
  199. #define MUL(x,y) ((t16 = (y)) ? (x=low16(x)) ? \
  200.         t32 = (word32)x*t16, x = low16(t32), t16 = t32>>16, \
  201.         x = x-t16+(x<t16) : \
  202.         (x = 1-t16) : (x = 1-x))
  203. #endif
  204. #endif
  205.  
  206. #ifdef USE_ASM
  207.  
  208. static void cipher_idea(word16 FAR *inblock, word16 FAR *outblock, IDEAkey zkey)
  209. {
  210.     word16 sx1, sx4, skk, done8;
  211.     __asm {
  212. ;A while ago I posted a message claiming a speed of 238,000
  213. ;bytes/sec for an implementation of IDEA on a 33Mh 486.  Below is
  214. ;an explanation and some code to show how it works.  The basic
  215. ;trick should be useful on many (but not all) processors.  I
  216. ;expect only those familiar with IDEA and its reference
  217. ;implementation will be able to follow the discussion.    See:
  218. ;
  219. ;Lai, Xueja and Massey, James L.  A Proposal for a New Block
  220. ;Encryption Standard, Eurocrypt 90
  221. ;
  222. ;For those who have been asking for the code, sorry I kept
  223. ;putting it off.  I wanted to get it out of Turbo Pascal
  224. ;ideal-mode, but I never had the time.
  225. ;
  226. ;Colin Plum wrote IDEA-386 code which is included in PGP
  227. ;2.3a and uses the same tricks.  I don't know who's is
  228. ;faster, but I expect they will be very close.    Now
  229. ;here's how it's done.
  230. ;
  231. ;A major bottleneck in software IDEA is the mul() routine, which
  232. ;is used 34 times per 64 bit block.  The routine performs
  233. ;multiplication in the multiplicative group mod 2^16+1.  The two
  234. ;factors are each in a 16 bit word, and the output is also in a 16
  235. ;bit word.    Note that 0 is not a member of the multiplicative
  236. ;group and 2^16 does not fit in 16 bits. We therefor use the 0
  237. ;word to represent 2^16.  Now group elements map one to one onto
  238. ;all possible 16 bit words, since 2^16+1 is prime.
  239. ;
  240. ;Here is (essentially) the reference implementation from [Lai].
  241. ;
  242. ;
  243. ;unsigned mul( unsigned a, unsigned b ) {
  244. ;  long int p ;
  245. ;  long unsigned q ;
  246. ;        if( a==0 ) p= 0x00010001 - b ;
  247. ;        else if( b==0 ) p= 0x00010001 - a ;
  248. ;        else {
  249. ;                q= a*b;
  250. ;                p= (q & 0xffff) - (q>>16)
  251. ;                if( p<0 ) p= p + 0x00010001 ;
  252. ;          }
  253. ;        return (unsigned)(p & 0xffff) ;
  254. ;}
  255. ;
  256. ;
  257. ;Note the method of reducing a 32 bit word modulo 2^16-1.  We
  258. ;subtract the high word from the low word, and add the modulus
  259. ;back if the result is less than 0.  [Lai] contains a proof that
  260. ;this works, and you can convince yourself fairly easily.
  261. ;
  262. ;To speed up this routine, we note that the tests for a=0 and b=0
  263. ;will rarely be false.    With the possible exception of the first 2
  264. ;of the 34 multiplications, 0 should be no more likely than any of
  265. ;the other 65535 numbers.  Note that if (and only if) either a or
  266. ;b is 0 then q will also be 0, and we can check for this in one
  267. ;instruction if our processor sets a zero flag for multiplication
  268. ;(as the 68000 does but 80x86 does not).
  269. ;
  270. ;Fortunately p will also be zero after the subtraction if and only
  271. ;if either a or b is 0.  Proof: r will be zero when the high order
  272. ;word of q equals the low order word, and that happens when q is
  273. ;divisible by 00010001 hex.  Since 00010001h = 2^16+1 is prime,
  274. ;this happens if either a or b is a multiple of 2^16+1, and 0 is
  275. ;the only such multiple which will fit in a 16 bit word.
  276. ;
  277. ;The speed-up strategy is to proceed under the assumption that a
  278. ;and b are not 0, check to be sure in one instruction, and
  279. ;recompute if the assumption was wrong.  Here's some 8086
  280. ;assembler code:
  281. ;
  282. ;        mov  ax, [a]
  283. ;        mul  [b]        ; ax is implied. q is now in DX AX
  284. ;        sub  ax, dx     ; mod 2^16+1
  285. ;        jnz  not0        ; Jump if neither op was 0. Usually taken.
  286. ;
  287. ;        mov  ax, 1        ; recompute result knowing one op is 0.
  288. ;        sub  ax, [a]
  289. ;        sub  ax, [b]
  290. ;        jmp  out        ; Just jump over adding the carry.
  291. ;not0:
  292. ;        adc  ax, 0        ; If r<0 add 1, otherwise do nothing.
  293. ;out:                 ; Result is now in ax
  294. ;
  295. ;
  296. ;Note that when r<0 we add 1 instead of 2^16+1 since the 2^16 part
  297. ;overflows out of the result.  The "adc  ax, 0" does all the work
  298. ;of checking for a negative result and adding the modulus if
  299. ;needed.
  300. ;
  301. ;The multiplication takes 9 instructions, 4 of which are rarely
  302. ;executed.    I believe similar tricks are possible on many
  303. ;processors.  The one drawback to the check-after-multiply tactic
  304. ;is that we can't let the multiply overwrite the only copy of an
  305. ;operand.
  306. ;
  307. ;Note that most software implementations of IDEA will run at
  308. ;slightly different speeds when 0's come up in the multiply
  309. ;routine.  The reference implementation is faster on 0, this one
  310. ;is faster on non-zero.  This may be a problem for some real-time
  311. ;stuff, and also suggests an attack based on timing.
  312. ;
  313. ;Finally, below is an implementation of the complete encryption
  314. ;function in 8086 assembler, to replace the cipher_idea() function
  315. ;in PGP.  It takes the same parameters as the function from PGP,
  316. ;and uses the c language calling conventions.  I tested it using
  317. ;the debug features of the idea.c file in PGP.    You will need to
  318. ;add segment/assume directives.  This version uses no global data
  319. ;and should be reentrant.
  320. ;
  321. ;The handling of zero multipliers is outside the inner loop so
  322. ;that a short conditional jump can loop back to the beginning.
  323. ;Forward conditional jumps are usually not taken and backward
  324. ;jumps are usually taken, which is consistent with 586 branch
  325. ;prediction (or so I've heard).  Stalls where the output of one
  326. ;instruction is needed for the next seem unavoidable.
  327. ;
  328. ;Last I heard, IDEA was patent pending.  My code is up for grabs,
  329. ;although I would get a kick out being credited if you use it.
  330. ;On the other hand Colin's code is already tested and ready
  331. ;to assemble and link with PGP.
  332. ;
  333. ;--Bryan
  334. ;
  335. ;____________________CODE STARTS BELOW THIS LINE_________
  336.  
  337. ;  Called as: cipher_idea(inbuff, outbuff, zkey)
  338. ;  All arguments must be near pointers addressed off DS.
  339.  
  340.  ;        push ax     ; My compiler assumes these are not saved.
  341.  ;        push bx
  342.  ;        push cx
  343.  ;        push dx
  344.  
  345.         push si
  346.         push di
  347.  
  348. ; Put the 16 bit sub-blocks in registers and/or local variables
  349.         mov  si, [inblock]
  350.         mov  ax, [si]
  351.         mov  [sx1], ax         ; x1  is in ax and sx1
  352.         mov  di, [si+2]      ; x2  is in di
  353.         mov  bx, [si+4]      ; x3  is in bx
  354.         mov  dx, [si+6]
  355.         mov  [sx4], dx         ; x4  is in sx4
  356.  
  357.         mov  si, [zkey]      ; si points to next subkey
  358.         mov  [done8], si
  359.         add  [done8], 96     ; we will be finished with 8 rounds
  360.                              ; when si=done8
  361.  
  362. LLloop:                      ; 8 rounds of this
  363.         add  di, [si+2]      ; x2+=zkey[2]    is in di
  364.         add  bx, [si+4]      ; x3+=zkey[4]    is in bx
  365.  
  366.         mul  [Word  ptr si]     ;x1 *= zkey[0]
  367.         sub  ax, dx
  368.         jz    LLx1             ; if 0, use special case multiply
  369.         adc  ax, 0
  370. LLx1out:
  371.         mov  [sx1], ax         ; x1 is in ax and sx1
  372.  
  373.         xor  ax, bx          ; ax= x1^x3
  374.         mul  [Word ptr si+8] ; compute kk
  375.         sub  ax, dx          ; if 0, use special case multiply
  376.         jz    LLkk
  377.         adc  ax, 0
  378. LLkkout:
  379.         mov  cx, ax          ; kk is in cx
  380.  
  381.         mov  ax, [sx4]         ; x4 *= zkey[6]
  382.         mul  [Word ptr si+6]
  383.         sub  ax, dx
  384.         jz     LLx4             ; if 0, use special case multiply
  385.         adc  ax, 0
  386. LLx4out:
  387.         mov  [sx4], ax         ; x4 is in sx4 and ax
  388.  
  389.         xor  ax, di          ; x4^x2
  390.         add  ax, cx          ; kk+(x2^x4)
  391.         mul  [Word ptr si+10]; compute t1
  392.         sub  ax, dx
  393.         jz    LLt1             ; if 0, use special case multiply
  394.         adc  ax, 0
  395. LLt1out:                     ; t1 is in ax
  396.  
  397.         add  cx, ax          ; t2 is in cx     kk+t1
  398.  
  399.         xor  [sx4], cx         ; x4 in sx4
  400.         xor  di, cx          ; new x3 in di
  401.         xor  bx, ax          ; new x2 in bx
  402.         xchg bx, di          ; x2 in di, x3 in bx
  403.         xor  ax, [sx1]         ; x1 in ax
  404.         mov  [sx1], ax         ; and [sx1]
  405.  
  406.         add  si, 12          ; point to next subkey
  407.         cmp  si, [done8]
  408.         jne  LLloop
  409.         jmp  LLout8
  410.  
  411. ;------------------------------------------
  412. ; Special case multiplications, when one factor is 0
  413.  
  414. LLx1:    mov  ax, 1
  415.         sub  ax, [sx1]
  416.         sub  ax, [Word ptr si]
  417.         jmp  LLx1out
  418.  
  419. LLkk:    mov  ax, [sx1]         ; rebuild overwritten operand
  420.         xor  ax, bx
  421.         neg  ax
  422.         inc  ax
  423.         sub  ax, [si+8]
  424.         jmp  LLkkout
  425.  
  426. LLx4:    mov  ax, 1
  427.         sub  ax, [sx4]
  428.         sub  ax, [Word ptr si+6]
  429.         jmp  LLx4out
  430.  
  431. LLt1:    mov  ax, [sx4]         ; rebuild
  432.         xor  ax, di
  433.         add  ax, cx
  434.         neg  ax
  435.         inc  ax
  436.         sub  ax, [si+10]
  437.         jmp  LLt1out
  438.  
  439. ;---------------------------------------------------
  440. ;    8 rounds are done, now that extra pseudo-round
  441.  
  442. LLout8:
  443.         push di
  444.         mov  di, [outblock]
  445.  
  446.         mul  [Word ptr si]
  447.         sub  ax, dx
  448.         jnz  LLo1n             ; jump over special case code
  449.         mov  ax, 1
  450.         sub  ax, [sx1]
  451.         sub  ax, [si]
  452.         jmp  LLo1out
  453. LLo1n:    adc  ax, 0
  454. LLo1out:  mov [di], ax         ; final ciphertext block 1
  455.  
  456.         mov  ax, [sx4]
  457.         mul  [Word ptr si+6]
  458.         sub  ax, dx
  459.         jnz  LLo4n             ; jump over special case code
  460.         mov  ax, 1
  461.         sub  ax, [sx4]
  462.         sub  ax, [si+6]
  463.         jmp  LLo4out
  464. LLo4n:    adc  ax, 0
  465. LLo4out: mov  [di+6], ax     ; final ciphertext block 4
  466.  
  467.         add  bx, [si+2]
  468.         mov  [di+2], bx      ; final ciphertext block 2
  469.         pop  ax
  470.         add  ax, [si+4]
  471.         mov  [di+4], ax      ; final ciphertext block 3
  472.  
  473. ;  Restore the stack and return
  474.  
  475.         pop  di
  476.         pop  si
  477. ;        pop  dx
  478. ;        pop  cx
  479. ;        pop  bx
  480. ;        pop  ax
  481.     }
  482. }
  483.  
  484. #else
  485.  
  486. /* IDEA encryption/decryption algorithm. In/out can be the same buffer */ 
  487.  
  488. static void cipher_idea(word16 FAR *in, word16 FAR *out, register CONST IDEAkey Z)
  489. {
  490.        register uint16 x1, x2, x3, x4, t1, t2;
  491.        register uint16 t16;
  492.        register word32 t32;
  493.        int r = ROUNDS;
  494.        x1 = *in++;    x2 = *in++;
  495.        x3 = *in++;    x4 = *in;
  496.        do
  497.        {
  498.              MUL(x1,*Z++);
  499.              x2 += *Z++;
  500.              x3 += *Z++;
  501.              MUL(x4, *Z++);
  502.              t2 = x1^x3;
  503.              MUL(t2, *Z++);
  504.              t1 = t2 + (x2^x4);
  505.              MUL(t1, *Z++);
  506.              t2 = t1+t2;
  507.              x1 ^= t1;
  508.              x4 ^= t2; 
  509.              t2 ^= x2;
  510.              x2 = x3^t1;
  511.              x3 = t2;
  512.        } while (--r);
  513.        MUL(x1, *Z++);
  514.        *out++ = x1;
  515.        *out++ = x3 + *Z++;
  516.        *out++ = x2 + *Z++;
  517.        MUL(x4, *Z);
  518.        *out = x4;
  519. }
  520. #endif
  521.  
  522. #ifdef TEST
  523.  
  524. /* Number of Kbytes of test data to encrypt. Defaults to 1 MByte. */
  525.  
  526. #ifndef KBYTES
  527. #define KBYTES 1024
  528. #endif
  529.  
  530. #ifndef CLOCKS_PER_SEC
  531. #define CLOCKS_PER_SEC 1000000
  532. #endif
  533.  
  534. int main()
  535. {       /* Test driver for IDEA cipher */ 
  536.        int i, j, k; 
  537.        IDEAkey Z, DK;
  538.        word16 XX[4], TT[4], YY[4];       
  539.        word16 userkey[8];
  540.        clock_t start, end;
  541.        long l;
  542.  
  543.        /* Make a sample user key for testing... */
  544.  
  545.        for(i=0; i<8; i++)
  546.              userkey[i] = i+1;
  547.  
  548.        /* Compute encryption subkeys from user key... */
  549.  
  550.        en_key_idea(userkey,Z);
  551.        printf("\nEncryption key subblocks: ");
  552.        for(j=0; j<ROUNDS+1; j++)
  553.        {
  554.              printf("\nround %d:   ", j+1);
  555.              if (j==ROUNDS)
  556.                     for(i=0; i<4; i++)
  557.                           printf(" %6u", Z[j*6+i]);
  558.              else
  559.                     for(i=0; i<6; i++)
  560.                           printf(" %6u", Z[j*6+i]);
  561.        }
  562.  
  563.        /* Compute decryption subkeys from encryption subkeys... */
  564.  
  565.        de_key_idea(Z,DK);
  566.        printf("\nDecryption key subblocks: ");
  567.        for(j=0; j<ROUNDS+1; j++)
  568.        {
  569.              printf("\nround %d:   ", j+1);
  570.              if (j==ROUNDS)
  571.                     for(i=0; i<4; i++)
  572.                           printf(" %6u", DK[j*6+i]);
  573.              else
  574.                     for(i=0; i<6; i++)
  575.                           printf(" %6u", DK[j*6+i]);
  576.        }
  577.  
  578.        /* Make a sample plaintext pattern for testing... */
  579.  
  580.        for (k=0; k<4; k++)
  581.              XX[k] = k;
  582.        printf("\n Encrypting %d KBytes (%ld blocks)...", KBYTES, KBYTES*64l);
  583.        fflush(stdout);
  584.        start = clock();
  585.        cipher_idea(XX,YY,Z);         /* encrypt plaintext XX, making YY */ 
  586.        for (l = 1; l < 64*KBYTES; l++)
  587.              cipher_idea(YY,YY,Z);     /* repeated encryption */
  588.        cipher_idea(YY,TT,DK);         /* decrypt ciphertext YY, making TT */ 
  589.        for (l = 1; l < 64*KBYTES; l++)
  590.              cipher_idea(TT,TT,DK);  /* repeated decryption */
  591.        end = clock() - start;
  592.        l = end * 1000. / CLOCKS_PER_SEC + 1;
  593.        i = l/1000;
  594.        j = l%1000;
  595.        l = KBYTES * 1024. * CLOCKS_PER_SEC / end;
  596.  
  597.        printf("%d.%03d seconds = %ld bytes per second\n", i, j, l);
  598.        printf("\nX %6u   %6u  %6u  %6u \n",    
  599.          XX[0], XX[1],    XX[2], XX[3]);
  600.        printf("Y %6u   %6u  %6u  %6u \n",
  601.          YY[0], YY[1],    YY[2], YY[3]);
  602.        printf("T %6u   %6u  %6u  %6u \n",
  603.          TT[0], TT[1],    TT[2], TT[3]);
  604.        /* Now decrypted TT should be same as original XX */
  605.        for (k=0; k<4; k++)
  606.              if (TT[k] != XX[k])
  607.              {
  608.                     printf("\n\07Error!  Noninvertable encryption.\n");
  609.                     exit(-1);       /* error exit */ 
  610.              }
  611.        printf("\nNormal exit.\n");
  612.        return 0;
  613. }
  614. #endif /* TEST */
  615.  
  616. /* xorbuf - change buffer via xor with random mask block. Used for Cipher 
  617.  * Feedback (CFB) or Cipher Block Chaining (CBC) modes of encryption. Can be
  618.  *    applied for any block encryption algorithm, with any block size, such as 
  619.  * the DES or the IDEA cipher.    */
  620.  
  621. static void xorbuf(register byteptr buf, register byteptr mask, register int count)
  622. /*       count must be > 0 */
  623. {
  624.        if (count) 
  625.              do
  626.                     *buf++ ^= *mask++;
  627.              while (--count);
  628. }       /* xorbuf */
  629.  
  630. /* cfbshift - shift bytes into IV for CFB input. Used only for Cipher Feedback
  631.  * (CFB) mode of encryption. Can be applied for any block encryption algorithm
  632.  * with any block size, such as the DES or the IDEA cipher.  */
  633.  
  634. static void cfbshift(register byteptr iv, register byteptr buf, register int count, int blocksize)
  635. /* iv is initialization vector. buf is buffer pointer. count is number of bytes
  636.  * to shift in...must be > 0. blocksize is 8 bytes for DES or IDEA ciphers. */
  637. {
  638.        int retained;
  639.        if (count)
  640.        {
  641.              retained = blocksize-count;   /* number bytes in iv to retain */
  642.          /* left-shift retained bytes of IV over by count bytes to make room */
  643.              while (retained--)
  644.              {
  645.                     *iv = *(iv+count);
  646.                     iv++;
  647.              }
  648.              /* now copy count bytes from buf to shifted tail of IV */
  649.              do     *iv++ = *buf++;
  650.              while (--count);
  651.        }
  652. }       /* cfbshift */
  653.  
  654. /* Key schedules for IDEA encryption and decryption */
  655.  
  656. static IDEAkey Z, DK;
  657. static word16 FAR *iv_idea;     /* pointer to IV for CFB or CBC */
  658. static boolean cfb_dc_idea;        /* TRUE iff CFB decrypting */
  659.  
  660. /* initkey_idea initializes IDEA for ECB mode operations */
  661.  
  662. void initkey_idea(byte FAR *key, boolean decryp)
  663. {
  664.        word16 userkey[8]; /* IDEA key is 16 bytes long */
  665.        int i;
  666.        /* Assume each pair of bytes comprising a word is ordered MSB-first. */
  667.        for (i=0; i<8; i++)
  668.        {
  669.              userkey[i] = (key[0]<<8) + key[1];
  670.              key++; key++;
  671.        }
  672.        en_key_idea(userkey,Z);
  673.        if (decryp)
  674.        {
  675.              de_key_idea(Z,Z);     /* compute inverse key schedule DK */
  676.        }
  677.        for (i=0; i<8; i++)/* Erase dangerous traces */
  678.              userkey[i] = 0;
  679. } /* initkey_idea */
  680.  
  681. /* Run a 64-bit block thru IDEA in ECB (Electronic Code Book) mode, using the
  682.  * currently selected key schedule. */
  683.  
  684. void idea_ecb(word16 FAR *inbuf, word16 FAR *outbuf)
  685. {
  686.        /* Assume each pair of bytes comprising a word is ordered MSB-first. */
  687. #ifndef HIGHFIRST    /* If this is a least-significant-byte-first CPU */
  688.        word16 x;
  689.        /* Invert the byte order for each 16-bit word for internal use. */
  690.        x = inbuf[0]; outbuf[0] = x >> 8 | x << 8;
  691.        x = inbuf[1]; outbuf[1] = x >> 8 | x << 8;
  692.        x = inbuf[2]; outbuf[2] = x >> 8 | x << 8;
  693.        x = inbuf[3]; outbuf[3] = x >> 8 | x << 8;
  694.        cipher_idea(outbuf, outbuf, Z);
  695.        x = outbuf[0]; outbuf[0] = x >> 8 | x << 8;
  696.        x = outbuf[1]; outbuf[1] = x >> 8 | x << 8;
  697.        x = outbuf[2]; outbuf[2] = x >> 8 | x << 8;
  698.        x = outbuf[3]; outbuf[3] = x >> 8 | x << 8;
  699. #else  /* HIGHFIRST */
  700.        /* Byte order for internal and external representations is the same. */
  701.        cipher_idea(inbuf, outbuf, Z);
  702. #endif /* HIGHFIRST */
  703. } /* idea_ecb */
  704.  
  705. /* initcfb - Initializes IDEA key schedule tables via key; initializes Cipher
  706.  * Feedback mode IV. References context variables cfb_dc_idea and iv_idea.    */
  707.  
  708. void initcfb_idea(word16 FAR *iv0, byte FAR *key, boolean decryp)
  709. /* iv0 is copied to global iv_idea, buffer will be destroyed by ideacfb. key is
  710.  * pointer to key buffer. decryp is TRUE if decrypting, FALSE if encrypting. */
  711. {
  712.        iv_idea = iv0;
  713.        cfb_dc_idea = decryp;
  714.        initkey_idea(key,FALSE);
  715. }
  716.  
  717. /* ideacfb - encipher a buffer with IDEA enciphering algorithm, using Cipher
  718.  *    Feedback (CFB) mode. Assumes initcfb_idea has already been called. 
  719.  * References context variables cfb_dc_idea and iv_idea.  */
  720.  
  721. void ideacfb(byteptr buf, int count)
  722. /* buf is input, output buffer, may be more than 1 block. count is byte count
  723.  * is byte count of buffer.  May be > IDEABLOCKSIZE. */
  724. {
  725.        int chunksize;                 /* smaller of count, IDEABLOCKSIZE */
  726.        word16 temp[IDEABLOCKSIZE/2];
  727.  
  728.        while ((chunksize = min(count,IDEABLOCKSIZE)) > 0)
  729.        {
  730.              idea_ecb(iv_idea,temp);  /* encrypt iv_idea, making temp. */ 
  731.              if (cfb_dc_idea)/* buf is ciphertext */
  732.                     /* shift in ciphertext to IV... */
  733.                     cfbshift((byte FAR *)iv_idea,buf,chunksize,IDEABLOCKSIZE);
  734.              /* convert buf via xor */
  735.              xorbuf(buf,(byte *)temp,chunksize);/* buf has enciphered output */
  736.              if (!cfb_dc_idea)/* buf was plaintext, is now ciphertext */
  737.                     /* shift in ciphertext to IV... */
  738.                     cfbshift((byte FAR *)iv_idea,buf,chunksize,IDEABLOCKSIZE);
  739.              count -= chunksize;
  740.              buf += chunksize;
  741.        }
  742. }
  743.  
  744. /* close_idea function erases all the key schedule information when we are 
  745.  * done with a set of operations for a particular IDEA key context. This is to
  746.  * prevent any sensitive data from being left around in memory. */
  747.  
  748. void close_idea(void)        /* erase current key schedule tables */
  749. {
  750.        short i;
  751.        for (i = 0; i < KEYLEN; i++)
  752.              Z[i] = 0;
  753. }       /* close_idea() */
  754.  
  755. /* These buffers are used by init_idearand, idearand, and close_idearand. */
  756. static word16 dtbuf_idea[4] = {0};       /* buffer for enciphered timestamp */
  757. static word16 randseed_idea[4] = {0};  /* seed for IDEA random # generator */
  758. static word16 randbuf_idea[4] = {0};   /* buffer for IDEA random # generator */
  759. static byte randbuf_idea_counter = 0;  /* random bytes left in randbuf_idea */
  760.  
  761. /* init_idearand - initialize idearand, IDEA random number generator. Used for
  762.  *    generating cryptographically strong random numbers. Much of design comes 
  763.  * from Appendix C of ANSI X9.17. key is pointer to IDEA key buffer. seed is 
  764.  * pointer to random number seed buffer. tstamp is a 32-bit timestamp */
  765.  
  766. void init_idearand(byte key[16], byte seed[8], word32 tstamp)
  767. {
  768.        int i;
  769.        initkey_idea(key, FALSE);      /* initialize IDEA */
  770.        for (i=0; i<4; i++)              /* capture timestamp material */
  771.        {     dtbuf_idea[i] = tstamp;  /* get bottom word */
  772.              tstamp = tstamp >> 16;   /* drop bottom word */
  773.              /* tstamp has only 4 bytes-- last 4 bytes will always be 0 */
  774.        }
  775.        /* Start with enciphered timestamp: */
  776.        idea_ecb(dtbuf_idea,dtbuf_idea);
  777.        /* initialize seed material */
  778.        for (i=0; i<8; i++)
  779.              ((byte *)randseed_idea)[i] = seed[i];
  780.        randbuf_idea_counter = 0; /* # of random bytes left in randbuf_idea */
  781. }
  782.  
  783. /* idearand - IDEA pseudo-random number generator. Used for generating 
  784.  * cryptographically strong random numbers. Much of design comes from Appendix
  785.  * C of ANSI X9.17.  */
  786.  
  787. byte idearand(void)
  788. {
  789.        int i;
  790.        if (randbuf_idea_counter==0)         /* if random buffer is spent...*/
  791.        {     /* Combine enciphered timestamp with seed material: */
  792.              for (i=0; i<4; i++)
  793.                     randseed_idea[i] ^= dtbuf_idea[i];
  794.              idea_ecb(randseed_idea,randbuf_idea);     /* fill new block */
  795.              /* Compute new seed vector: */
  796.              for (i=0; i<4; i++)
  797.                     randseed_idea[i] = randbuf_idea[i] ^ dtbuf_idea[i];
  798.              idea_ecb(randseed_idea,randseed_idea);    /* fill new seed */
  799.              randbuf_idea_counter = 8;     /* reset counter for full buffer */
  800.        }
  801.        /* Take a byte from randbuf_idea: */
  802.        return(((byte *)randbuf_idea)[--randbuf_idea_counter]);
  803. }
  804.  
  805. void close_idearand(void)
  806. {       /* Erase random IDEA buffers and wipe out IDEA key info */
  807.        int i;
  808.        for (i=0; i<4; i++)
  809.        {     randbuf_idea[i] = 0;
  810.              randseed_idea[i] = 0;
  811.              dtbuf_idea[i] = 0;
  812.        }
  813.        close_idea();/* erase current key schedule tables */
  814. }
  815.